package leetcode.top100;

import leetcode.a_总结分布.Code06_二叉树相关拓展;
import utils.TreeNode;

/**
 * 给定一个非空二叉树，返回其最大路径和。
 * <p>
 * 本题中，路径被定义为一条从树中任意节点出发，
 * <p>
 * 达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。
 * <p>
 * 示例 1:
 * <p>
 * 输入: [1,2,3]
 * <p>
 * 1
 * / \
 * 2   3
 * <p>
 * 输出: 6
 * 示例 2:
 * <p>
 * 输入: [-10,9,20,null,null,15,7]
 * <p>
 *    -10
 *    / \
 *   9  20
 *     /  \
 *    15   7
 * <p>
 * 输出: 42
 * <p>
 * <p>
 * 分析：二叉树的最大路径和是基于以下两种情况产生的：
 * Case1：左孩子+右孩子+当前节点形成路径
 * Case2：当前节点+Math.max(左孩子，右孩子) ，把这个结果返回给父节点，作为父节点的孩子。
 * <p>
 * 特别需要注意的是，case1中是没有递归的，只能全局统计。
 * 每次更新case1和case2的最大值为res，case2递归给上层。
 * <p>
 * 如果case1也递归，拿上面第二个例子说，20左侧递归是15，此时res已经更新为15.
 * 如果此时res为递归返回结果，那么20的右孩子返回max(res,7)=15，最后答案是50.
 * 事实上，case1不可以递归，也就是res是全局更新的。
 * 只能递归case2.
 * <p>
 * 相同递归思想的题目{@link Code06_二叉树相关拓展#height()}
 *
 * @date 2020/4/11 22:37
 */
public class Code124_MaxTreePathSum_二叉树最大路径和 {

    private Integer res = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        process1(root);
        return res;
    }

    /**
     * 后序遍历处理左右孩子的结果
     */
    private int process1(TreeNode root) {
        if (root == null) return 0;
        //左孩子，如果是负数则不要，也就是+0
        int left = Math.max(0, process1(root.left));
        //右孩子
        int right = Math.max(0, process1(root.right));
        //返回两种情况
        //case1:左右孩子+当前节点为路径.case1不能递归
        res = Math.max(res, left + right + root.val);
        //case2:左右孩子中最大值+当前节点，返回给父节点。
        int case2 = Math.max(left, right) + root.val;

        //事实上这里不需要更新res，因为case2还会返回给上层，res会更新到case2和res
        res = Math.max(res, case2);

        //只能递归case2给上层节点,不能直接返回res!
        return case2;
    }

    private int process2(TreeNode root) {
        if (root == null) return 0;
        //左孩子，如果是负数则不要，也就是+0
        int left = Math.max(0, process2(root.left));
        //右孩子
        int right = Math.max(0, process2(root.right));
        //返回两种情况
        //case1:左右孩子+当前节点为路径.case1不能递归
        res = Math.max(res, left + right + root.val);
        //case2:左右孩子中最大值+当前节点，返回给父节点。
        //只能递归case2给上层节点,不能直接返回res!
        return Math.max(left, right) + root.val;
    }

    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(-10);
        treeNode.left = new TreeNode(9);
        treeNode.right = new TreeNode(20);
        treeNode.right.left = new TreeNode(15);
        treeNode.right.right = new TreeNode(7);
        System.out.println(new Code124_MaxTreePathSum_二叉树最大路径和().maxPathSum(treeNode));
    }
}
